package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/product-of-array-except-self/
 *
 * @author tzp
 * @since 2020/10/18
 */
public class LC238 implements TwoProblem {

    //On时间, O1空间
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, 1);
        int leftJi = 1;
        for (int i = 1; i < nums.length; i++) {
            leftJi = leftJi * nums[i - 1];
            result[i] = result[i] * leftJi;
        }

        int rightJi = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            rightJi = rightJi * nums[i + 1];
            result[i] = result[i] * rightJi;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC238().productExceptSelf(new int[]{1, 2, 3, 4, 5})));
    }
}
